package no22;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/25 15:04
 * 链表中的倒数第 k 个节点
 * https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
 */
public class Solution {

    // 节点类
    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    // 获取链表的倒数第 k 个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 边界判断
        if (head == null || k <= 0) {
            return null;
        }
        // 依次定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 先让快指针向前走 k 步, 走完后快慢指针就相差了 k 步
        while (k > 0 && fast != null) {
            fast = fast.next;
            k--; // 可能节点数不足 k 个, 这样循环结束后 k 就不为0
        }
        // 快慢指针同时向后走, 当快指针指向链表末尾 null 时, 慢指针即指向倒数第 k 个节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 返回节点需要对 k 进行判断
        return k > 0 ? null : slow;
    }
}
